package 堆结构常见题;

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author ljb
 * @version 1.0
 * @Date 2024/11/24
 */
// 最多线段重合问题
// 测试链接 : https://www.nowcoder.com/practice/1ae8d0b6bb4e4bcdbf64ec491f63fc37
// 测试链接 : https://leetcode.cn/problems/meeting-rooms-ii/
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
public class Code02_MaxCover {

    public static int MAXN = 10001;
    public static int n;
    public static int[][] lines = new int[MAXN][2];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            n = (int)in.nval;
            for(int i = 0; i < n; i++){
                in.nextToken();
                lines[i][0] = (int)in.nval;
                in.nextToken();
                lines[i][1] = (int)in.nval;
            }
            out.print(compute());
        }
        out.flush();
        out.close();
        br.close();
    }

    public static int compute(){
    //    堆的清空
        size = 0;
        // 线段一共有n条，line[0...n-1][2] : line[i][0] line[i][1], 左闭右闭
        // 所有线段，根据开始位置排序(lines[i][0])，结束位置无所谓
        // 比较器的用法
        // line [0...n) 排序 : 所有小数组，开始位置谁小谁在前
        Arrays.sort(lines, 0, n, (a, b) -> a[0] - b[0]);
        int ans = 0;
        for(int i = 0; i < n; i++){
            // i : line[i][0] line[i][1]
            while(size > 0 && heap[0] <= lines[i][0]){
                pop();
            }
            add(lines[i][1]);
            ans = Math.max(ans, size);
        }
        return ans;
    }

//    小根堆，堆顶0位置
    public static int[] heap = new int[MAXN];

//    堆的大小
    public static int size;

    //相当于堆排序中的heapInsert，对于新加入堆中的元素，维持小根堆
    public static void add(int x){
        heap[size] = x;
        int i = size++;
        while(heap[i] < heap[(i-1)/2]){
            swap(i, (i-1)/2);
            i = (i-1)/2;
        }
    }

    //相当于堆排序中的heapIfy，这里是将小根堆的堆顶去掉，让最后一个元素替代，重新维持小根堆
    public static void pop(){
        swap(0, --size);
        int i = 0, l = 1;
        while(l < size){
            int best = l+1 < size && heap[l+1] < heap[l] ? l+1 : l;
            best = heap[i] > heap[best] ? best : i;
            if(best == i){
                break;
            }
            swap(i, best);
            i = best;
            l = 2*i+1;
        }
    }

    public static void swap(int i, int j){
        int tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }

    // 也找到了leetcode测试链接-会员题，需要付费
    // 测试链接 : https://leetcode.cn/problems/meeting-rooms-ii/
    // 提交如下代码可以直接通过
    public static int minMeetingRooms(int[][] meeting){
        int n = meeting.length;
        Arrays.sort(meeting, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int ans = 0;
        for(int i = 0; i < n; i++){
            while(!heap.isEmpty() && heap.peek() <= meeting[i][0]){
                heap.poll();
            }
            heap.add(meeting[i][1]);
            ans = Math.max(ans, heap.size());
        }
        return ans;
    }

    // 上面的leetcode题目是会员题，需要付费
    // 如果不想开通leetcode会员，还有一个类似的题，但是注意题意，和课上讲的有细微差别
    // 课上讲的题目，认为[1,4]、[4、5]可以严丝合缝接在一起，不算有重合
    // 但是如下链接的题目，认为[1,4]、[4、5]有重合部分，也就是4
    // 除此之外再无差别
    // 测试链接 : https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/
    // 提交如下代码可以直接通过

    /**
     * 想象每条线段根据开始和结束位置，放在x轴上，然后有一根竖线，
     * 从左到右划过x轴，竖线压中的线段上的点，就需要把当前点放入到某个组里。
     * 请问，从左到右划的过程，你最多需要准备几个组？最多重合几条线段，就需要几个组。
     * 这些组不断复用空间，放入不同的点。但是最大重合了多少，你就需要准备几个组。
     * @param meeting
     * @return
     */
    /**
     * 假设最大线段重合是3，在分组时这3条线段就不可能放到同一个组里，
     * 就必须准备3个组来放置他们。因为最大重合数是3，所以最大分组也必须是3，
     * 少于3就放不下了。
     * @param meeting
     * @return
     */
    public static int minGroups(int[][] meeting){
        int n = meeting.length;
        Arrays.sort(meeting, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int ans = 0;
        for(int i = 0; i < n; i++){
            while(!heap.isEmpty() && heap.peek() < meeting[i][0]){
                heap.poll();
            }
            heap.add(meeting[i][1]);
            ans = Math.max(ans, heap.size());
        }
        return ans;
    }
}
